package com.example.demo.utils;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * @ClassName LinkedLRUCache
 * @Author lys4134
 * @Date 2021/08/03 14:10:07
 * @Description LinkedLRUCache
 * @Version 1.0
 **/
public class LinkedLRUCache<K, V> {
    private int capacity;
    private Map<K, LRUNode> map;
    private LRUNode head;
    private LRUNode tail;

    LinkedLRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
    }

    public synchronized void put(K k, V v) {
        LRUNode node = map.get(k);
        // 存在该 key，将节点的设置为 head
        if (node != null) {
            node.value = v;
            remove(node, false);
        } else {
            /**
             * 该节点不存在
             * 1、将该节点加入缓存
             * 2、设置该节点为 head
             * 3、判断是否超出容量
             */
            node = new LRUNode(k, v);
            if (map.size() >= capacity) {
                //删除 tail 节点
                remove(tail, true);
            }
            map.put(k, node);
            setHead(node);
        }
        // 设置当前节点为首节点
        setHead(node);
    }

    public Object get(String key) {
        LRUNode node = map.get(key);
        if (node != null) {
            // 将刚操作的元素放到head
            remove(node, false);
            setHead(node);
            return node.value;
        }
        return null;
    }

    /**
     * 设置头结点
     *
     * @param node
     */
    private void setHead(LRUNode node) {
        if (head != null) {
            node.next = head;
            head.prev = node;
        }
        head = node;
        if (tail == null) {
            tail = node;
        }
    }

    /**
     * 从链表中删除此Node
     *
     * @param node
     * @param flag 为 true 就删除该节点的 key
     */
    private void remove(LRUNode node, boolean flag) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
        node.next = null;
        node.prev = null;
        if (flag) {
            map.remove(node.key);
        }
    }

    private Iterator iterator() {
        return map.keySet().iterator();
    }

    private class LRUNode<K, V> {
        /**
         * cache 的 key
         */
        private K key;
        /**
         * cache 的 value
         */
        private V value;
        private LRUNode next;
        private LRUNode prev;

        LRUNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);

        lruCache.put("1", "a");
        lruCache.put("2", "b");
        lruCache.put("3", "c");
        lruCache.put("4", "d");
        lruCache.put("5", "e");

        System.out.println("插入 5 个元素");
        println(lruCache);
        System.out.println("插入 3 元素");
        lruCache.put("3", "c");
        println(lruCache);
        System.out.println("插入第  6 个元素");
        lruCache.put("6", "f");
        println(lruCache);
        System.out.println("访问 4 元素");
        lruCache.get("4");
        println(lruCache);
    }

    private static void println(LRUCache lruCache) {
        Iterator iterator = lruCache.keyIterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + "    ");
        }

        System.out.println();
    }
}